package extra;

public class LinkStackComplet {

    private Node top;

    public LinkStackComplet() {
        top = null;
    }

    public boolean empty() {
        return top == null;
    }

    public boolean full() {
        return false;
    }

    public void push(Object e) {
        Node tmp = new Node(e);
        tmp.next = top;
        top = tmp;
    }

    public Object pop() {

        Object e = top.data;
        top = top.next;
        return e;
    }

    public Object peek() {

        Object e = top.data;

        return e;
    }

    public void matching(String x) {
        LinkStackComplet S = new LinkStackComplet();

        for (int i = 0; i < x.length(); i++) {
            char c = x.charAt(i);
            if (c == '(') {
                S.push(c);
            } else {
                if (c == ')') {
                    if (S.empty()) {
                        System.out.println("NOT MATCHING !!!");
                    } else {
                        S.pop();
                    }
                }
            }
        }
        if (!S.empty()) {
            System.out.println("NOT MATCHING !!!");
        } else {
            System.out.println("MATCHING !!!");
        }
    }

    public void Evaluation(String x) {

        LinkStackComplet S = new LinkStackComplet();
        for (int i = 0; i < x.length(); i++) {
            char c = x.charAt(i);
            String s = "0" + c;

            if (c == '+') {
                int z = Integer.parseInt((String) S.pop()) + Integer.parseInt((String) S.pop());
                S.push(Integer.toString(z));
            } else if (c == '*') {
                int z = Integer.parseInt((String) S.pop()) * Integer.parseInt((String) S.pop());
                S.push(Integer.toString(z));

            } else if (c == '/') {
                int u = Integer.parseInt((String) S.pop());

                int z = Integer.parseInt((String) S.pop()) / u;
                S.push(Integer.toString(z));

            } else if (c == '-') {
                int u = Integer.parseInt((String) S.pop());
                int z = Integer.parseInt((String) S.pop()) - u;
                S.push(Integer.toString(z));
            } else {
                S.push(s);
            }
        }
        System.out.println("THE POSTFIX = " + x);
        System.out.println("THE RESULT = " + S.pop());
    }
    public void postfix(String x) {
        String output = "";
        LinkStackComplet S = new LinkStackComplet();
        for (int i = 0; i < x.length(); i++) {
            char c = x.charAt(i);

            if (c == ('+') || c == ('*') || c == ('-') || c == ('/')) {
                while (!S.empty() && priority(S.peek()) >= priority(c)) {
                    output += S.pop();
                }
                S.push(c);
            } else if (c == '(') {
                S.push(c);
            } else if (c == ')') {
                while (!S.peek().equals('(')) {
                    output += S.pop();
                }
                S.pop();
            } else {
                output += c;
            }
        }
        while (!S.empty()) {
            output += S.pop();
        }
        System.out.println("THE INFIX = " + x);
        System.out.println("THE POSTFIX = " + output);
    }

    public int priority(Object x) {
        if (x.equals('+') || x.equals('-')) {
            return 1;
        } else if (x.equals('*') || x.equals('/')) {
            return 2;
        } else {
            return 0;
        }
    }

    public static void main(String args[]) {
        LinkStackComplet s = new LinkStackComplet();
        s.postfix("A*B+((C+D)*(F-G))");
        System.out.println("------------------------------------------");
        s.matching("A*B+((C+D)*(F-G))");
        System.out.println("------------------------------------------");
        s.Evaluation("23*23+32-*+");
        System.out.println("------------------------------------------");
    }
}

